/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wangxin
 * Date: 2024-12-19
 * Time: 17:04
 */
public class MyRBTree {
    static class RBTreeNode{
        private int val;
        private RBTreeNode left;
        private RBTreeNode right;
        private RBTreeNode parent;
        private Color color;
        public RBTreeNode(int val){
            this.val = val;
            this.color = Color.RED;
        }
    }
    public RBTreeNode root;
    public boolean insert(int val){
        RBTreeNode node = new RBTreeNode(val);
        if(root == null){
            root = node;
            root.color = Color.BLACK;
            return true;
        }
        RBTreeNode parent = null;
        RBTreeNode cur = root;
        while(cur != null){

            if(cur.val > val){
                parent = cur;
                cur = cur.left;
            }else if(cur.val == val){
                return false;
            }else{
                parent = cur;
                cur = cur.right;
            }
        }
        if(parent.val > val){
            parent.left = node;
        }else{
            parent.right = node;
        }
        node.parent = parent;
        cur = node;
        while(parent!=null&&parent.color == Color.RED) {
            RBTreeNode grandfather = parent.parent;
            if (grandfather.left == parent) {
                RBTreeNode uncle = grandfather.right;
                if (uncle != null && uncle.color == Color.RED) {
                    uncle.color = Color.BLACK;
                    parent.color = Color.BLACK;
                    grandfather.color = Color.RED;
                    cur = grandfather;
                    parent = cur.parent;

                } else {
                    if (cur == parent.right) {
                        rotateLeft(parent);
                        RBTreeNode temp = parent;
                        parent = cur;
                        cur = temp;
                    }
                    rotateRight(grandfather);
                    grandfather.color = Color.RED;
                    parent.color = Color.BLACK;
                }
            } else {
                RBTreeNode uncle = grandfather.left;
                if (uncle != null && uncle.color == Color.RED) {
                    uncle.color = Color.BLACK;
                    parent.color = Color.BLACK;
                    grandfather.color = Color.RED;
                    cur = grandfather;
                    parent = cur.parent;

                } else {
                    if (cur == parent.left) {
                        rotateRight(parent);
                        RBTreeNode temp = parent;
                        parent = cur;
                        cur = temp;
                    }
                    rotateLeft(grandfather);
                    grandfather.color = Color.RED;
                    parent.color = Color.BLACK;
                }
            }
        }
        root.color = Color.BLACK;
        return  true;
    }
    public void rotateRight(RBTreeNode parent){
        RBTreeNode subL = parent.left;
        RBTreeNode subLR = subL.right;
        parent.left = subLR;
        subL.right = parent;
        if(subLR != null){
            subLR.parent = parent;
        }
        RBTreeNode pParent = parent.parent;
        parent.parent = subL;
        if(parent == root){
            root = subL;
            root.parent = null;
        }else{
            if(pParent.left == parent){
                pParent.left = subL;
            }else{
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
    }
    public void rotateLeft(RBTreeNode parent){
        RBTreeNode subR = parent.right;
        RBTreeNode subRL = subR.left;
        parent.right = subRL;
        subR.left = parent;
        if(subRL!= null){
            subRL.parent = parent;
        }
        RBTreeNode pParent = parent.parent;
        parent.parent = subR;
        if(parent == root){
            root = subR;
            root.parent = null;
        }else{
            if(pParent.left == parent){
                pParent.left = subR;
            }else{
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
    }
    public void inorder(RBTreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }
    public boolean isRBTree(){
        if(root == null){
            return true;
        }
        if(root.color != Color.BLACK){
            System.out.println("违反了红黑树性质：根节点是黑色的");
            return false;
        }
        int blankNum = 0;
        RBTreeNode cur = root;
        while(cur != null){
            if(cur.color == Color.BLACK){
                blankNum++;
            }
            cur = cur.left;
        }
        return checkRB(root)&&checkBlankNum(root,0,blankNum);
    }
    private boolean checkRB(RBTreeNode root){
        if(root == null){
            return true;
        }
        if(root.color == Color.RED&&root.parent != null&&root.parent.color == Color.RED){
            System.out.println("违反了红黑树性质：没有两个连续的红色节点");
            return false;
        }
        return checkRB(root.left)&&checkRB(root.right);
    }
    private boolean checkBlankNum(RBTreeNode root,int blankPathNum,int blankNum){
        if(root == null){
            return true;
        }
        if(root.color == Color.BLACK){
            blankPathNum++;
        }
        if(root.left == null&&root.right == null){
            if(blankNum!=blankPathNum){
                System.out.println("违反了红黑树性质：所有含叶子节点的路径应包含相同数目的黑色节点");
                return false;
            }
        }
        return checkBlankNum(root.left,blankPathNum,blankNum)&&checkBlankNum(root.right,blankPathNum,blankNum);
    }
}
